#include <iostream>
#include <math.h>
#include <vector>

using namespace std;

int TIME = 0;
vector<int> w;
vector<int> p;
int COUNT = 0;
int W = 0;
int maxprofit = 0;

void SortLists(vector<int> &w, vector<int> &v, int n) 
{
	int *wvArray = new int[n + 1];
	int *wArray = new int[n + 1];
	int *vArray = new int[n + 1];
	for (int i = 0; i < n; i ++)
	{
		wArray[i] = w[i];
		vArray[i] = v[i];
		wvArray[i] = (v[i]/w[i]);
	}
	for (int p=1; p < n; p++) 
	{
		for (int i=0; i < n-p; i++)
		{
			if (wvArray[i] > wvArray[i+1]) 
			{
				int tmp = wvArray[i]; 
				wvArray[i] = wvArray[i+1]; 
				wvArray[i+1] = tmp;
				tmp = wArray[i];
				wArray[i] = wArray[i+1];
				wArray[i+1] = tmp;
				tmp = vArray[i];
				vArray[i] = vArray[i+1];
				vArray[i+1] = tmp;
			}
		}
	}
	w.clear();
	v.clear();
	for (int i = 0; i < n; i ++)
	{
		w.push_back(wArray[i]);
		v.push_back(vArray[i]);
	}
}

bool PromisingK (int i, int profit, int weight)
{
	int j, k;
	int totweight;
	float bound;
	if (weight >= W)
	{
		return false;
		TIME ++;
	}

	else
	{
		j = i + 1;
		bound = profit;
		totweight = weight;
		while (j < COUNT && totweight + w[j] <= W)
		{
			totweight = totweight + w[j];
			bound = bound + p[j];
			j++;
			TIME ++;
		}
		k = j;
		if (k < COUNT)
		{
			bound += (W - totweight) * p[k]/w[k];
			TIME++;
		}
		return bound > maxprofit;
	}
}

void Knapsack (int i, int profit, int weight, int& numbest, vector<int>& include, vector<int>& bestset)
{
	if (weight <= W && profit > maxprofit)
	{
		maxprofit = profit;
		numbest = i;
		copy(include.begin(), include.end(), bestset.begin());
		TIME ++;
	}

	if (PromisingK(i, profit, weight))
	{
		TIME ++;
		include[i + 1] = 1;
		Knapsack(i + 1, profit + p[i + 1], weight + w[i + 1], numbest, include, bestset);
		include[i + 1] = 0;
		Knapsack(i + 1, profit, weight, numbest, include, bestset);
	}
}


bool Promising (int i, int* col)
{
	int k = 1;
	while ( k < i)
	{
		TIME++;
		if (col[i] == col[k] || abs(col[i] - col[k]) == i - k)
		{
			return false;
		}
		k++;
	}
	return true;
}

void Queens (int i, int n, int* col)
{
	int j;
	TIME ++;
	if (Promising(i, col))
	{
		if (i == n)
		{
			for (int x = 2; x <= n; x++)
			{
				int tmp = col[x];
				cout << col[x];
				TIME ++;
			}
			cout << "\n";
		}
		else
		{
			for (j = 1; j <= n-1; j++)
			{
				col[i + 1] = j;
				Queens(i + 1, n, col);
				TIME ++;
			}
		}
	}
}


int main()
{
	int n = 0;
	cout << "\nEnter the number of queens to test: ";
	cin >> n;
	n += 1;
	int* col = new int[n];
	for (int x = 1; x < n; x++)
	{
		col[x] = 0;
	}
	cout << "\nSolutions are: " << endl;
	Queens (1, n, col);
	cout << "\nThe time complexity is " << TIME;
	int profit;
	int weight;
	COUNT = 0;
	
	cout << "\n\nStarting Knapsack";
	cout << "\n\nEnter in the Knapsacks weight capacity: ";
	cin >> W;
	w.push_back(0);
	p.push_back(0);
	do
	{
		cout << "\nPlease enter the Weight of item" << COUNT + 1 << ": ";
		cin >> weight;
		if (weight > 0)
		{
			cout << "\nPlease enter the Price of item" << COUNT + 1 << ": ";
			cin >> profit;
			w.push_back(weight);
			p.push_back(profit);
			COUNT ++;
		}
	}while(weight > 0);
	COUNT++;
	int numbest = 0;
	vector<int> bestset(COUNT);
	vector<int> include(COUNT);
	TIME = 0;
	Knapsack(0, 0, 0, numbest, include, bestset);
	for (int i = 1; i < COUNT; i ++)
	{
		cout << "\n" << i << ":\t" << bestset[i];
	}
	cout << "\nThe maxprofit is: " << maxprofit;
	cout << "\nThe running time is: " << TIME;
	system("Pause");
	return 0;
}